
\chapter{Mathematical formulas as code. I. Nameless functions\label{chap:1-Values,-types,-expressions,}}

\section{Translating mathematics into code}

\subsection{First examples}

We begin by implementing some computational tasks in Scala.

\subsubsection{Example \label{subsec:Example-Factorial-of-10}\ref{subsec:Example-Factorial-of-10}:
Factorial of 10}

Find the product of integers from $1$ to $10$ (the \textbf{factorial\index{factorial function}}
of 10).

First, we write a mathematical formula for the result:
\[
\prod_{k=1}^{10}k\quad.
\]
We can then write Scala code in a way that resembles this formula:
\begin{lstlisting}
scala> (1 to 10).product
res0: Int = 3628800
\end{lstlisting}

The code \texttt{}\lstinline!(1 to 10).product! is an \textbf{expression}\index{expression},
which means that (1) the code can be evaluated (e.g., using the Scala
interpreter) and yields a value, and (2) the code can be used inside
a larger expression. For example, we could write
\begin{lstlisting}
scala> 100 + (1 to 10).product + 100   // This code contains `(1 to 10).product` as a sub-expression.
res0: Int = 3629000

scala> 3628800 == (1 to 10).product 
res1: Boolean = true
\end{lstlisting}
The Scala interpreter indicates that the result of \texttt{}\lstinline!(1 to 10).product!
is a value $3628800$ of type \lstinline!Int!. If we need to define
a name for that value, we use the \textsf{``}\lstinline!val!\textsf{''} syntax:
\begin{lstlisting}
scala> val fac10 = (1 to 10).product
fac10: Int = 3628800
\end{lstlisting}


\subsubsection{Example \label{subsec:Example-Factorial-as-a-function}\ref{subsec:Example-Factorial-as-a-function}:
Factorial as a function}

Define a function that takes an integer $n$ and computes the factorial
of $n$.

A mathematical formula for this function can be written as
\[
f\left(n\right)=\prod_{k=1}^{n}k\quad.
\]
The corresponding Scala code is
\begin{lstlisting}
def f(n: Int) = (1 to n).product
\end{lstlisting}

In Scala\textsf{'}s \texttt{}\lstinline!def! syntax, we need to specify the
type of a function\textsf{'}s argument; in this case, we write \lstinline!n: Int!.
In the usual mathematical notation, types of arguments are either
not written at all, or written separately from the formula:
\begin{equation}
f(n)=\prod_{k=1}^{n}k,\quad\forall n\in\mathbb{N}\quad.\label{eq:factorial-as-function}
\end{equation}
Equation~(\ref{eq:factorial-as-function}) indicates that $n$ must
be from the set of positive integers, denoted by $\mathbb{N}$ in
mathematics. This is similar to specifying the type \texttt{}\lstinline!Int!
in the Scala code. So, the argument\textsf{'}s type in the code specifies the
\textbf{domain} of a function\index{domain of a function} (the set
of admissible arguments).

Having defined the function \lstinline!f!, we can now apply it to
an integer argument: 
\begin{lstlisting}
scala> f(10)
res6: Int = 3628800
\end{lstlisting}
It is a \textbf{type error}\index{type error} to apply \lstinline!f!
to a non-integer value:
\begin{lstlisting}
scala> f("abc")
<console>:13: error: type mismatch;
 found   : String("abc")
 required: Int
\end{lstlisting}


\subsection{Nameless functions\label{subsec:Nameless-functions}}

Both the code written above and Eq.~(\ref{eq:factorial-as-function})
involve \emph{naming} the function as \textsf{``}$f$\textsf{''}. Sometimes a function
does not really need a name, \textemdash{} say, if the function is
used only once. \textsf{``}Nameless\textsf{''} mathematical functions may be denoted
using the symbol $\rightarrow$ (pronounced \textsf{``}maps to\textsf{''}) like this:
\[
x\rightarrow\left(\text{some formula}\right)\quad.
\]
So the mathematical notation for the nameless factorial function is
\[
n\rightarrow\prod_{k=1}^{n}k\quad.
\]
This reads as \textsf{``}a function that maps $n$ to the product of all $k$
where $k$ goes from $1$ to $n$\textsf{''}. The Scala expression implementing
this mathematical formula is
\begin{lstlisting}
(n: Int) => (1 to n).product
\end{lstlisting}
This expression shows Scala\textsf{'}s syntax for a \textbf{nameless function}\index{nameless function}.
Here, 
\begin{lstlisting}
n: Int
\end{lstlisting}
is the function\textsf{'}s \textbf{argument}, while
\begin{lstlisting}
(1 to n).product
\end{lstlisting}
is the function\textsf{'}s \textbf{body}. The function arrow (\lstinline!=>!)
separates the argument from the body.\footnote{In mathematics, the \textsf{``}maps to\textsf{''} symbol is $\mapsto$, but this book
uses a simpler arrow symbol $\rightarrow$ that is visually similar.
Many programming languages use the symbols \lstinline!->! or \lstinline!=>!
for the function arrow; see Table~\ref{lambda-functions-table}.} 

Functions in Scala (whether named or nameless) are treated as values\index{function value},
which means that we can also define a Scala value as
\begin{lstlisting}
scala> val fac = (n: Int) => (1 to n).product
fac: Int => Int = <function1>
\end{lstlisting}
We see that the value \lstinline!fac! has the type \lstinline!Int => Int!,
which means that the function \lstinline!fac! takes an integer (\lstinline!Int!)
argument and returns an integer result value. What is the value of
the function \lstinline!fac! \emph{itself}? As we have just seen,
the Scala interpreter prints \lstinline!<function1>! as the \textsf{``}value\textsf{''}
of \lstinline!fac!. An alternative Scala interpreter, \texttt{ammonite}\footnote{\texttt{\href{https://ammonite.io/}{https://ammonite.io/}}},
prints something like this,
\begin{lstlisting}
scala@ val fac = (n: Int) => (1 to n).product
fac: Int => Int = ammonite.$sess.cmd0$$$Lambda$1675/2107543287@1e44b638
\end{lstlisting}
The long number could indicate an address in memory.

One may imagine that a \textsf{``}function value\textsf{''} represents a block\emph{
}of compiled code that will actually run and evaluate the function\textsf{'}s
body when the function is applied to its argument.

Once defined, a function can be applied to an argument like this:
\begin{lstlisting}
scala> fac(10)
res1: Int = 3628800
\end{lstlisting}

However, functions can be used without naming them. We can directly
apply a nameless factorial function to an integer argument \lstinline!10!
instead of writing \lstinline!fac(10)!:
\begin{lstlisting}
scala> ((n: Int) => (1 to n).product)(10)
res2: Int = 3628800
\end{lstlisting}
One would not often write code like this because there is no advantage
in creating a nameless function and then applying it right away to
an argument. This is because we can evaluate the expression
\begin{lstlisting}
((n: Int) => (1 to n).product)(10)
\end{lstlisting}
by substituting \lstinline!10! instead of \lstinline!n! in the function
body, which gives us
\begin{lstlisting}
(1 to 10).product
\end{lstlisting}

If a nameless function uses the argument several times, for example
\begin{lstlisting}
((n: Int) => n*n*n + n*n)(12345)
\end{lstlisting}
it is still better to substitute the argument and to eliminate the
nameless function. We could write
\begin{lstlisting}
12345*12345*12345 + 12345*12345
\end{lstlisting}
but, of course, it is better to avoid repeating the value \lstinline!12345!.
To achieve that, we may define \texttt{}\lstinline!n! as a value
in an \textbf{expression block\index{expression block}} like this:
\begin{lstlisting}
scala> { val n = 12345; n*n*n + n*n }
res3: Int = 322687002
\end{lstlisting}
Defined in this way, the value \lstinline!n! is visible only within
the expression block. Outside the block, another value named \lstinline!n!
could be defined independently of this \lstinline!n!. For this reason,
the definition of \lstinline!n! is called a \textbf{locally}\index{local scope}
\textbf{scoped} definition.

Nameless functions are convenient when they are themselves arguments
of other functions, as we will see next.

\subsubsection{Example \label{subsec:Example-prime-numbers}\ref{subsec:Example-prime-numbers}:
prime numbers}

Define a function that takes an integer argument $n$ and determines
whether $n$ is a prime number.

A simple mathematical formula for this function can be written as
\begin{equation}
\text{isPrime}\left(n\right)=\forall k\in\left[2,n-1\right].\ (n\%k)\neq0\quad.\label{eq:is_prime_def}
\end{equation}
This formula has two clearly separated parts: first, a range of integers
from $2$ to $n-1$, and second, a requirement that all these integers
should satisfy a given condition, $(n\%k)\neq0$. Formula~(\ref{eq:is_prime_def})
is translated into Scala code as
\begin{lstlisting}
def isPrime(n: Int) = (2 to n-1).forall(k => n % k != 0)
\end{lstlisting}
In this code, the two parts of the mathematical formula are implemented
in a way that is closely similar to the mathematical notation, except
for the arrow after $k$.

We can now apply the function \lstinline!isPrime! to some integer
values:
\begin{lstlisting}
scala> isPrime(12)
res3: Boolean = false

scala> isPrime(13)
res4: Boolean = true
\end{lstlisting}
As we can see from the output above, the function \lstinline!isPrime!
returns a value of type \lstinline!Boolean!. Therefore, the function
\lstinline!isPrime! has type \lstinline!Int => Boolean!.

A function that returns a \lstinline!Boolean! value is called a \textbf{predicate}\index{predicate}.

In Scala, it is strongly recommended (although often not mandatory)
to specify the return type of named functions. The required syntax
looks like this,
\begin{lstlisting}
def isPrime(n: Int): Boolean = (2 to n-1).forall(k => n % k != 0)
\end{lstlisting}

However, we do not need to specify the type \texttt{}\lstinline!Int!
for the argument \texttt{}\lstinline!k! of the nameless function
\lstinline*k => n % k != 0*. The Scala compiler knows that \texttt{}\lstinline!k!
is going to iterate over the \emph{integer} elements of the range
\lstinline!(2 to n-1)!, which effectively forces \texttt{}\lstinline!k!
to be of type \lstinline!Int!.

\subsection{Nameless functions and bound variables}

The code for \texttt{}\lstinline!isPrime! differs from the mathematical
formula\ (\ref{eq:is_prime_def}) in two ways.

One difference is that the interval $\left[2,n-1\right]$ is in front
of \lstinline!forall!. Another is that the Scala code uses a nameless
function \lstinline*(k => n % k != 0)*, while Eq.~(\ref{eq:is_prime_def})
does not seem to involve any functions.

To understand the first difference, we need to keep in mind that the
Scala syntax such as \texttt{}\lstinline!(2 to n-1).forall(k => ...)!
means to apply a function called \texttt{}\lstinline!forall! to
\emph{two} arguments: the first argument is the range \texttt{}\lstinline!(2 to n-1)!\texttt{,}
and the second argument is the nameless function \lstinline!(k => ...)!.
In Scala, the \textbf{method} syntax\index{method syntax} \lstinline!x.f(z)!,
and the equivalent \textbf{infix} syntax\index{infix syntax} \lstinline!x f z!,
means that a function \texttt{}\lstinline!f! is applied to its \emph{two}
arguments, \texttt{}\lstinline!x! and \lstinline!z!. In the ordinary
mathematical notation, this would be $f(x,z)$. Infix notation is
widely used when it is easier to read: for instance, we write $x+y$
rather than something like $plus\,(x,y)$.

A single-argument function could be also defined as a method, and
then the syntax is \lstinline!x.f!, as in the expression \texttt{}\lstinline!(1 to n).product!
we have seen before.

The methods \texttt{}\lstinline!product! and \texttt{}\lstinline!forall!
are already provided in the Scala standard library, so it is natural
to use them. If we want to avoid the method syntax, we could define
a function \texttt{}\lstinline!forAll! with two arguments and write
code like this,\hfill{}~ \begin{wrapfigure}{l}{0.4\columnwidth}%
\vspace{-0.8\baselineskip}
\begin{lstlisting}
forAll(2 to n-1, k => n % k != 0)
\end{lstlisting}

\vspace{-1.5\baselineskip}
\end{wrapfigure}%
This would bring the syntax closer to Eq.\ (\ref{eq:is_prime_def}). 

However, there still remains the second difference: The symbol $k$
is used as an \emph{argument} of a nameless function \lstinline*(k => n % k != 0)*
in the Scala code, while the mathematical formula 
\begin{equation}
\forall k\in\left[2,n-1\right].\ (n\%k)\neq0\label{eq:prime-formula-function}
\end{equation}
does not seem to use any functions but defines the symbol $k$ that
goes over the range $\left[2,n-1\right]$. The variable $k$ is then
used for writing the predicate $(n\%k)\neq0$. 

Let us investigate the role of $k$ more closely. The mathematical
variable $k$ is actually defined \emph{only inside} the expression
\textsf{``}$\forall k:...$\textsf{''} and makes no sense outside that expression.
This becomes clear by looking at Eq.\ (\ref{eq:is_prime_def}): The
variable $k$ is not present in the left-hand side and could not possibly
be used there. The name \textsf{``}$k$\textsf{''} is defined only in the right-hand
side, where it is first mentioned as the arbitrary element $k\in\left[2,n-1\right]$
and then used in the sub-expression \textsf{``}$n\%k$\textsf{''}.

So, the mathematical notation in Eq.~(\ref{eq:prime-formula-function})
says two things: First, we use the name $k$ for integers from $2$
to $n-1$. Second, for each of those $k$ we evaluate the expression
$n\neq0\text{ mod }k$, which can be viewed as a certain given \emph{function}
\emph{of} $k$ that returns a \lstinline!Boolean! value. Translating
the mathematical notation into code, it is therefore natural to use
the nameless function
\[
k\rightarrow(n\%k)\neq0
\]
and to write Scala code applying this nameless function to each element
of the range $\left[2,n-1\right]$ and checking that all result values
be \lstinline!true!:\hfill{}~ \begin{wrapfigure}{l}{0.4\columnwidth}%
\vspace{-0.8\baselineskip}
\begin{lstlisting}
(2 to n-1).forall(k => n % k != 0)
\end{lstlisting}

\vspace{-1.5\baselineskip}
\end{wrapfigure}%
Just as the mathematical notation defines the variable $k$ only in
the right-hand side of Eq.\ (\ref{eq:is_prime_def}), the argument
\lstinline!k! of the nameless Scala function \lstinline*k => n % k != 0*
is defined only within that function\textsf{'}s body and cannot be used in
any code outside the expression \lstinline*n % k != 0*.

Variables that are defined only inside an expression and are invisible
outside are called \textbf{bound variables}\index{bound variable|textit},
or \textsf{``}variables bound in an expression\textsf{''}. Variables that are used
in an expression but are defined outside it are called \textbf{free
variables}\index{free variable}, or \textsf{``}variables occurring free in
an expression\textsf{''}. These concepts apply equally well to mathematical
formulas and to Scala code. For example, in the mathematical expression
$k\rightarrow(n\%k)\neq0$ (which is a nameless function), the variable
$k$ is bound (it is defined only within that expression) but the
variable $n$ is free (it is defined outside that expression).

The main difference between free and bound variables is that bound
variables can be \emph{locally renamed} at will, unlike free variables.
To see this, consider that we could rename $k$ to $z$ and write
instead of Eq.\ (\ref{eq:is_prime_def}) an equivalent definition
\[
\text{isPrime}\left(n\right)=\forall z\in\left[2,n-1\right].\ (n\%z)\neq0\quad,
\]
or in Scala code,\hfill{}~ \begin{wrapfigure}{l}{0.4\columnwidth}%
\vspace{-0.8\baselineskip}
\begin{lstlisting}
(2 to n-1).forall(z => n % z != 0)
\end{lstlisting}

\vspace{-1.5\baselineskip}
\end{wrapfigure}%
The argument \lstinline!z! in the nameless function \lstinline*z => n % z != 0*
may be renamed without changing the result of the entire program.
No code outside that function needs to be changed after renaming \lstinline!z!.
But the value \lstinline!n! is defined outside and cannot be renamed
\textsf{``}locally\textsf{''} (i.e., only within the sub-expression). If we wanted
to rename \lstinline!n! in the sub-expression \lstinline*z => n % z != 0*,
we would also need to change all other code that defines and uses
\lstinline!n! \emph{outside} that expression, or else the program
would become incorrect.

Mathematical formulas use bound variables in various constructions
such as $\forall k:p(k)$, $\exists k:p(k)$, $\sum_{k=a}^{b}f(k)$,
$\int_{0}^{1}k^{2}dk$, $\lim_{n\rightarrow\infty}f(n)$, and $\text{argmax}_{k}f\left(k\right)$.
When translating mathematical expressions into code, we need to recognize
the presence of bound variables, which the mathematical notation does
not make quite so explicit. For each bound variable, we need to create
a nameless function whose argument is that variable, e.g., \lstinline!k=>p(k)!
or \lstinline!k=>f(k)! for the examples just shown. Only then will
our code correctly reproduce the behavior of bound variables in mathematical
expressions.

As an example, the mathematical formula $\forall k\in\left[1,n\right].\,p\left(k\right)$
has a bound variable $k$ and is translated into Scala code as

\begin{lstlisting}
(1 to n).forall(k => p(k))
\end{lstlisting}
At this point we can apply a simplification trick to this code. The
nameless function $k\rightarrow p(k)$ does exactly the same thing
as the (named) function $p$: It takes an argument, which we may call
$k$, and returns $p(k)$. So, we can simplify the Scala code above
to

\begin{lstlisting}
(1 to n).forall(p)
\end{lstlisting}

The simplification of $x\rightarrow f(x)$ to just $f$ is always
possible for functions $f$ of a single argument.\footnote{Certain features of Scala allow programmers to write code that looks
like \lstinline!f(x)! but actually involves additional implicit or
default arguments of the function \lstinline!f!, or an implicit type
conversion for its argument \lstinline!x!. In those cases, replacing
the code \lstinline!x => f(x)! by \lstinline!f! will fail to compile.
But these complications do not arise when working with simple functions.}

\section{Aggregating data from sequences}

Consider the task of counting how many even numbers there are in a
given list $L$ of integers. For example, the list $\left[5,6,7,8,9\right]$
contains \emph{two} even numbers: $6$ and $8$.

A mathematical formula for this task can be written like this,
\begin{align*}
\text{countEven}\left(L\right) & =\sum_{k\in L}\text{isEven}\left(k\right)\quad,\\
\text{isEven}\left(k\right) & =\begin{cases}
1 & \text{if }(k\%2)=0\quad,\\
0 & \text{otherwise}\quad.
\end{cases}
\end{align*}
Here we defined a helper function \texttt{}\lstinline!isEven! in
order to write more easily a formula for \lstinline!countEven!. In
mathematics, complicated formulas are often split into simpler parts
by defining helper expressions. 

We can write the Scala code similarly. We first define the helper
function \lstinline!isEven!; the Scala code can be written in a style
quite similar to the mathematical formula:

\begin{lstlisting}
def isEven(k: Int): Int = (k % 2) match {
  case 0 => 1 // First, check if it is zero.
  case _ => 0 // The underscore matches everything else.
}
\end{lstlisting}

For such a simple computation, we could also write shorter code using
a nameless function,

\begin{lstlisting}
val isEven = (k: Int) => if (k % 2 == 0) 1 else 0
\end{lstlisting}

Given this function, we now need to translate into Scala code the
expression $\sum_{k\in L}\text{is\_even}\left(k\right)$. We can represent
the list $L$ using the data type \lstinline!List[Int]! from the
Scala standard library.

To compute $\sum_{k\in L}\text{is\_even}\left(k\right)$, we must
apply the function \texttt{}\lstinline!isEven! to each element of
the list $L$, which will produce a list of some (integer) results,
and then we will need to add all those results together. It is convenient
to perform these two steps separately. This can be done with the functions
\texttt{}\lstinline!map! and \lstinline!sum!, defined in the Scala
standard library as methods for the data type \lstinline!List!.

The method \texttt{}\lstinline!sum! is similar to \lstinline!product!
and is defined for any \lstinline!List! of numerical types (\lstinline!Int!,
\lstinline!Float!, \lstinline!Double!, etc.). It computes the sum
of all numbers in the list:
\begin{lstlisting}
scala> List(1, 2, 3).sum
res0: Int = 6
\end{lstlisting}

The method \texttt{}\lstinline!map! needs more explanation. This
method takes a \emph{function} as its second argument, applies that
function to each element of the list, and puts all the results into
a \emph{new }list, which is then returned as the result value:

\begin{lstlisting}
scala> List(1, 2, 3).map(x => x*x + 100*x)
res1: List[Int] = List(101, 204, 309)
\end{lstlisting}

In this example, the argument of \lstinline!map! is the nameless
function $x\rightarrow x^{2}+100x$. This function will be used repeatedly
by \texttt{}\lstinline!map! to transform each integer from \lstinline!List(1, 2, 3)!,
creating a new list as a result.

It is equally possible to define the transforming function separately,
give it a name, and then use it as the argument to \lstinline!map!:
\begin{lstlisting}
scala> def func1(x: Int): Int = x*x + 100*x
func1: (x: Int)Int 

scala> List(1, 2, 3).map(func1)
res2: List[Int] = List(101, 204, 309)
\end{lstlisting}
Short functions are often defined inline, while longer functions are
defined separately with a name.

A method, such as \lstinline!map!, can be also used with a \textsf{``}dotless\textsf{''}
(infix) syntax:
\begin{lstlisting}
scala> List(1, 2, 3) map func1
res3: List[Int] = List(101, 204, 309)
\end{lstlisting}

If the transforming function \lstinline!func1! is used only once,
and especially for a simple operation such as $x\rightarrow x^{2}+100x$,
it is easier to work with a nameless function.

We can now combine the methods \texttt{}\lstinline!map! and \texttt{}\lstinline!sum!
to define \lstinline!countEven!:

\begin{lstlisting}
def countEven(s: List[Int]) = s.map(isEven).sum
\end{lstlisting}

This code can be also written using a nameless function instead of
\lstinline!isEven!:

\begin{lstlisting}
def countEven(s: List[Int]): Int = s
    .map { k => if (k % 2 == 0) 1 else 0 }
    .sum
\end{lstlisting}

It is customary in Scala to use methods when chaining several operations.
For instance \lstinline!s.map(...).sum! means first apply \lstinline!s.map(...)!,
which returns a \emph{new} list, and then apply \texttt{}\lstinline!sum!
to that list. To make the code more readable, we put each of the chained
methods on a new line. 

To test this code, let us run it in the Scala interpreter. In order
to let the interpreter work correctly with code entered line by line,
the dot character needs to be at the \emph{end} of the line. (In compiled
code, the dots may be at the beginning of line since the compiler
reads the entire code at once.)
\begin{lstlisting}
scala> def countEven(s: List[Int]): Int = s.
         map { k => if (k % 2 == 0) 1 else 0 }.
         sum
countEven: (s: List[Int])Int

scala> countEven(List(1,2,3,4,5))
res0: Int = 2

scala> countEven( List(1,2,3,4,5).map(x => x * 2) )
res1: Int = 5
\end{lstlisting}
Note that the Scala interpreter prints the types differently for named
functions (i.e., functions declared using \lstinline!def!). It prints
\lstinline!(s: List[Int])Int! for a function of type \lstinline!List[Int] => Int!.

\section{Filtering and truncating a sequence }

In addition to the methods \lstinline!sum!, \lstinline!product!,
\lstinline!map!, \texttt{}\lstinline!forall! that we have already
seen, the Scala standard library defines many other useful methods.
We will now take a look at using the methods \lstinline!max!, \lstinline!min!,
\lstinline!exists!, \lstinline!size!, \lstinline!filter!, and \lstinline!takeWhile!. 

The methods \lstinline!max!, \lstinline!min!, and \texttt{}\lstinline!size!
are self-explanatory:
\begin{lstlisting}
scala> List(10, 20, 30).max
res2: Int = 30

scala> List(10, 20, 30).min
res3: Int = 10

scala> List(10, 20, 30).size
res4: Int = 3
\end{lstlisting}

The methods \lstinline!forall!, \lstinline!exists!, \lstinline!filter!,
and \texttt{}\lstinline!takeWhile! require a predicate as an argument.
The \texttt{}\lstinline!forall! method returns \texttt{}\lstinline!true!
if and only if the predicate returns \lstinline!true! for all values
in the list; the \texttt{}\lstinline!exists! method returns \texttt{}\lstinline!true!
if and only if the predicate holds (returns \lstinline!true!) for
at least one value in the list. These methods can be written as mathematical
formulas like this:
\begin{align*}
\text{forall}\left(S,p\right) & =\forall k\in S.~p(k)=\text{true}\\
\text{exists}\left(S,p\right) & =\exists k\in S.~p(k)=\text{true}
\end{align*}
However, there is no mathematical notation for operations such as
\textsf{``}removing elements from a list\textsf{''}, so we will focus on the Scala
syntax for these functions.

The \lstinline!filter! method returns a list that contains only the
values for which the predicate returns \texttt{}\lstinline!true!:

\begin{lstlisting}
scala> List(1, 2, 3, 4, 5).filter(k => k % 3 != 0)
res5: List[Int] = List(1, 2, 4, 5)
\end{lstlisting}

The \texttt{}\lstinline!takeWhile! method truncates a given list,
returning a new list with the initial portion of values from the original
list for which predicate remains \lstinline!true!:
\begin{lstlisting}
scala> List(1, 2, 3, 4, 5).takeWhile(k => k % 3 != 0)
res6: List[Int] = List(1, 2)
\end{lstlisting}

In all these cases, the predicate\textsf{'}s argument, \lstinline!k!, must
be of the same type as the elements in the list. In the examples shown
above, the elements are integers (i.e., the lists have type \lstinline!List[Int]!),
therefore \texttt{}\lstinline!k! must be of type \lstinline!Int!.

The methods \lstinline!max!, \lstinline!min!, \lstinline!sum!,
and \texttt{}\lstinline!product! are defined on lists of \emph{numeric
types}, such as \lstinline!Int!, \lstinline!Double!, and \lstinline!Long!.
The other methods are defined on lists of all types.

Using these methods, we can solve many problems that involve transforming
and aggregating data stored in lists (as well as in arrays, sets,
or other similar data structures). In this context, a \textbf{transformation\index{data transformation}}
is a function taking a list of values and returning another list of
values; examples of transformation functions are \texttt{}\lstinline!filter!
and \lstinline!map!. An \textbf{aggregation\index{aggregation}}
is a function taking a list of values and returning a \emph{single}
value; examples of aggregation functions are \texttt{}\lstinline!max!
and \lstinline!sum!.

Writing programs by chaining together various methods of transformation
and aggregation is known as programming in the \textbf{map/reduce}\index{map/reduce programming style@\texttt{map}/\texttt{reduce} programming style}
\textbf{style}.

\section{Solved examples\index{solved examples}}

\subsection{Aggregation\label{subsec:Aggregation-solved-examples}}

\subsubsection{Example \label{subsec:ch1-aggr-Example-1}\ref{subsec:ch1-aggr-Example-1}}

Improve the code for \lstinline!isPrime! by limiting the search to
$k^{2}\leq n$:
\[
\text{isPrime}\left(n\right)=\forall k\in\left[2,n-1\right]\text{ such that if }k^{2}\leq n\text{ then }(n\%k)\neq0\quad.
\]


\subparagraph{Solution:}

Use \lstinline!takeWhile! to truncate the initial list when $k^{2}\leq n$
becomes false:
\begin{lstlisting}
def isPrime(n: Int): Boolean =
  (2 to n-1)
    .takeWhile(k =>   k*k <= n)
    .forall(k =>    n % k != 0)
\end{lstlisting}


\subsubsection{Example \label{subsec:ch1-aggr-Example-2}\ref{subsec:ch1-aggr-Example-2}}

Compute this product of absolute values: $\prod_{k\in\left[1,10\right]}\left|\sin\left(k+2\right)\right|$.

\subparagraph{Solution}

~
\begin{lstlisting}
(1 to 10)
  .map(k => math.abs(math.sin(k + 2)))
  .product
\end{lstlisting}


\subsubsection{Example \label{subsec:ch1-aggr-Example-3}\ref{subsec:ch1-aggr-Example-3}}

Compute $\sum_{k\in[1,10];~\cos k>0}\sqrt{\cos k}$.

\subparagraph{Solution}

~

\begin{lstlisting}
(1 to 10)
  .filter(k => math.cos(k) > 0)
  .map(k => math.sqrt(math.cos(k)))
  .sum
\end{lstlisting}
It is safe to compute $\sqrt{\cos k}$, because we have first filtered
the list by keeping only values $k$ for which $\cos k>0$. Let us
check that this is so:
\begin{lstlisting}
scala> (1 to 10).toList.filter(k => math.cos(k) > 0).map(x => math.cos(x))
res0: List[Double] = List(0.5403023058681398, 0.28366218546322625, 0.9601702866503661, 0.7539022543433046)
\end{lstlisting}


\subsubsection{Example \label{subsec:ch1-aggr-Example-4}\ref{subsec:ch1-aggr-Example-4}}

Compute the average of a non-empty list of type \lstinline!List[Double]!,
\[
\text{average}\left(s\right)=\frac{1}{n}\sum_{i=0}^{n-1}s_{i}\quad.
\]


\subparagraph{Solution}

We need to divide the sum by the length of the list:
\begin{lstlisting}
def average(s: List[Double]): Double = s.sum / s.size

scala> average(List(1.0, 2.0, 3.0))
res0: Double = 2.0
\end{lstlisting}


\subsubsection{Example \label{subsec:ch1-aggr-Example-5-Wallis-product}\ref{subsec:ch1-aggr-Example-5-Wallis-product}}

Given $n$, compute the Wallis product\index{Wallis product}\footnote{\texttt{\href{https://en.wikipedia.org/wiki/Wallis_product}{https://en.wikipedia.org/wiki/Wallis\_product}}}
truncated up to $\frac{2n}{2n+1}$: 
\[
\text{wallis}\left(n\right)=\frac{2}{1}\frac{2}{3}\frac{4}{3}\frac{4}{5}\frac{6}{5}\frac{6}{7}...\frac{2n}{2n+1}\quad.
\]


\subparagraph{Solution}

Define the helper function \lstinline!wallis_frac(i)! that computes
the $i^{\text{th}}$ fraction. The method \texttt{}\lstinline!toDouble!
converts integers to \texttt{}\lstinline!Double! numbers.
\begin{lstlisting}
def wallis_frac(i: Int): Double = (2*i).toDouble/(2*i - 1)*(2*i)/(2*i + 1)

def wallis(n: Int) = (1 to n).map(wallis_frac).product

scala> math.cos(wallis(10000))  // Should be close to 0.
res0: Double = 3.9267453954401036E-5

scala> math.cos(wallis(100000)) // Should be even closer to 0.
res1: Double = 3.926966362362075E-6
\end{lstlisting}
The limit of the Wallis product is $\frac{\pi}{2}$, so the cosine
of \lstinline!wallis(n)! tends to zero in the limit of large $n$.

\subsubsection{Example \label{subsec:ch1-aggr-Example-6}\ref{subsec:ch1-aggr-Example-6}}

Check numerically that $\sum_{k=1}^{\infty}\frac{1}{k^{2}}=\frac{\pi^{2}}{6}$.
First, define a function of $n$ that computes a partial sum of that
series until $k=n$. Then compute the partial sum for a large value
of $n$ and compare with the limit value.

\subparagraph{Solution}

~

\begin{lstlisting}
def euler_series(n: Int): Double = (1 to n).map(k => 1.0/k/k).sum

scala> euler_series(100000)
res0: Double = 1.6449240668982423

scala> val pi = 4*math.atan(1)
pi: Double = 3.141592653589793

scala> pi*pi/6
res1: Double = 1.6449340668482264 
\end{lstlisting}


\subsubsection{Example \label{subsec:ch1-aggr-Example-7}\ref{subsec:ch1-aggr-Example-7}}

Check numerically the infinite product formula
\[
\prod_{k=1}^{\infty}\left(1-\frac{x^{2}}{k^{2}}\right)=\frac{\sin\pi x}{\pi x}\quad.
\]


\subparagraph{Solution}

Compute this product up to $k=n$ for $x=0.1$ with a large value
of $n$, say $n=10^{5}$, and compare with the right-hand side:
\begin{lstlisting}
def sine_product(n: Int, x: Double): Double = (1 to n).map(k => 1.0 - x*x/k/k).product

scala> sine_product(n = 100000, x = 0.1) // Arguments may be named, for clarity.
res0: Double = 0.9836317414461351

scala> math.sin(pi*0.1)/pi/0.1
res1: Double = 0.9836316430834658
\end{lstlisting}


\subsubsection{Example \label{subsec:ch1-aggr-Example-8}\ref{subsec:ch1-aggr-Example-8}}

Define a function $p$ that takes a list of integers and a function
\lstinline!f: Int => Int!, and returns the largest value of $f(x)$
among all $x$ in the list.

\subparagraph{Solution}

~

\begin{lstlisting}
def p(s: List[Int], f: Int => Int): Int = s.map(f).max
\end{lstlisting}
Here is a test for this function:
\begin{lstlisting}
scala> p(List(2, 3, 4, 5), x => 60 / x)
res0: Int = 30
\end{lstlisting}


\subsection{Transformation}

\subsubsection{Example \label{subsec:ch1-Example-1}\ref{subsec:ch1-Example-1}}

Given a list of lists, \lstinline!s: List[List[Int]]!, select the
inner lists of size at least $3$. The result must be again of type
\lstinline!List[List[Int]]!. 

\subparagraph{Solution}

To \textsf{``}select the inner lists\textsf{''} means to compute a \emph{new} list
containing only the desired inner lists. We use \texttt{}\lstinline!filter!
on the outer list \lstinline!s!. The predicate for the filter is
a function that takes an inner list and returns \texttt{}\lstinline!true!
if the size of that list is at least $3$. Write the predicate as
a nameless function, \lstinline!t => t.size >= 3!, where \texttt{}\lstinline!t!
is of type \lstinline!List[Int]!:
\begin{lstlisting}
def f(s: List[List[Int]]): List[List[Int]] = s.filter(t => t.size >= 3)

scala> f(List( List(1,2), List(1,2,3), List(1,2,3,4) ))
res0: List[List[Int]] = List(List(1, 2, 3), List(1, 2, 3, 4)) 
\end{lstlisting}
The Scala compiler deduces the type of \lstinline!t! from the code;
no other type would work since we apply \lstinline!filter! to a \emph{list
of lists} of integers.

\subsubsection{Example \label{subsec:ch1-Example-2}\ref{subsec:ch1-Example-2}}

Find all integers $k\in\left[1,10\right]$ such that there are at
least three different integers $j$, where $1\leq j\leq k$, each
$j$ satisfying the condition $j^{2}>2k$.

\subparagraph{Solution}

~

\begin{lstlisting}
scala> (1 to 10).toList.filter(k => (1 to k).filter(j => j*j > 2*k).size >= 3)
res0: List[Int] = List(6, 7, 8, 9, 10) 
\end{lstlisting}
The argument of the outer \lstinline!filter! is a nameless function
that also uses a \lstinline!filter!. The inner expression

\noindent \begin{wrapfigure}{l}{0.45\columnwidth}%
\vspace{-0.8\baselineskip}
\begin{lstlisting}
(1 to k).filter(j => j*j > 2*k).size >= 3
\end{lstlisting}

\vspace{-1.5\baselineskip}
\end{wrapfigure}%
 (shown at left) computes the list of $j$\textsf{'}s that satisfy the condition
$j^{2}>2k$, and then compares the size of that list with $3$. In
this way, we impose the requirement that there should be at least
$3$ values of $j$. We can see how the Scala code closely follows
the mathematical formulation of the task.

\section{Summary}

Functional programs are mathematical formulas translated into code.
Table~\ref{tab:translating-mathematics-into-code} shows how to implement
some often used mathematical constructions in Scala.

\begin{table}
\begin{centering}
\begin{tabular}{|c|c|}
\hline 
\textbf{Mathematical notation} & \textbf{Scala code}\tabularnewline
\hline 
\hline 
$x\rightarrow\sqrt{x^{2}+1}$ & \lstinline!x => math.sqrt(x*x + 1)!\tabularnewline
\hline 
list $\left[1,~2,~...,~n\right]$ & \lstinline!(1 to n)!\tabularnewline
\hline 
list $\left[f(1),~...,~f(n)\right]$ & \lstinline!(1 to n).map(k => f(k))!\tabularnewline
\hline 
$\sum_{k=1}^{n}k^{2}$ & \lstinline!(1 to n).map(k => k*k).sum!\tabularnewline
\hline 
$\prod_{k=1}^{n}f(k)$ & \lstinline!(1 to n).map(f).product!\tabularnewline
\hline 
$\forall k\in[1,...,n].~p(k)\text{ holds}$ & \lstinline!(1 to n).forall(k => p(k))!\tabularnewline
\hline 
$\exists k\in[1,...,n].\:p(k)\text{ holds}$ & \lstinline!(1 to n).exists(k => p(k))!\tabularnewline
\hline 
${\displaystyle \sum_{k\in S\text{ such that }p(k)\text{ holds}}}f(k)$ & \lstinline!s.filter(p).map(f).sum!\tabularnewline
\hline 
\end{tabular}
\par\end{centering}
\caption{Translating mathematics into code.\label{tab:translating-mathematics-into-code}}
\end{table}

What problems can one solve with this knowledge?
\begin{itemize}
\item Compute mathematical expressions involving sums, products, and quantifiers,
based on integer ranges, such as $\sum_{k=1}^{n}f(k)$.
\item Transform and aggregate data from lists using \lstinline!map!, \lstinline!filter!,\textbf{
}\lstinline!sum!, and other methods from the Scala standard library.
\end{itemize}
What are examples of problems that are \emph{not} solvable with these
tools?
\begin{itemize}
\item Example~1: Compute the smallest $n\geq1$ such that 
\[
f(f(f(...f(0)...)>1000\quad,
\]
where the given function $f$ is applied $n$ times.
\item Example~2: Given a list $s$ of numbers, compute the list $r$ of
running averages: 
\[
r_{n}=\frac{1}{n}\sum_{k=0}^{n-1}s_{k}\quad.
\]
\item Example~3: Perform binary search over a sorted list of integers.
\end{itemize}
These computations involve a general case of \emph{mathematical induction}\index{mathematical induction}. 

Library functions we have seen so far, such as \texttt{}\lstinline!map!
and \lstinline!filter!, implement a restricted class of iterative
operations on lists: namely, operations that process each element
of a given list independently and accumulate results. In those cases,
the number of iterations is known (or at least bounded) in advance.
For instance, when computing \lstinline!s.map(f)!, the number of
function applications is given by the size of the initial list. However,
Example\ 1 requires applying a function $f$ repeatedly until a given
condition holds \textemdash{} that is, repeating for an \emph{initially
unknown} number of times. So it is impossible to write an expression
containing \lstinline!map!, \lstinline!filter!, \lstinline!takeWhile!,
etc., that solves Example\ 1. We could write the solution of Example\ 1
as a formula by using mathematical induction, but we have not yet
seen how to implement that in Scala code. 

Example\ 2 can be formulated as a definition of a new list $r$ by
induction: the base case is $r_{0}=s_{0}$, and the inductive step
is $r_{i}=s_{i}+r_{i-1}$ for $i=1,2,3,...$ However, operations such
as \texttt{}\lstinline!map! and \texttt{}\lstinline!filter! cannot
compute $r_{i}$ depending on the value of $r_{i-1}$.

Example\ 3 defines the search result by induction: the list is split
in half, and search is performed recursively (i.e., using the inductive
hypothesis) in the half that contains the required value. This computation
requires an initially unknown number of steps.

Chapter\ \ref{chap:2-Mathematical-induction} explains how to implement
these tasks using recursion.

\section{Exercises\label{sec:beginner-Exercises}\index{exercises}}

\subsection{Aggregation}

\subsubsection{Exercise \label{subsec:ch1-aggr-Exercise-1}\ref{subsec:ch1-aggr-Exercise-1}}

Machin\textsf{'}s formula\index{Machin\textsf{'}s formula}\footnote{\texttt{\href{http://turner.faculty.swau.edu/mathematics/materialslibrary/pi/machin.html}{http://turner.faculty.swau.edu/mathematics/materialslibrary/pi/machin.html}}}
converges to $\pi$ faster than Example~\ref{subsec:ch1-aggr-Example-5-Wallis-product}:
\begin{align*}
\frac{\pi}{4} & =4\arctan\frac{1}{5}-\arctan\frac{1}{239}\quad,\\
\arctan\frac{1}{n} & =\frac{1}{n}-\frac{1}{3}\frac{1}{n^{3}}+\frac{1}{5}\frac{1}{n^{5}}-...=\sum_{k=0}^{\infty}\frac{\left(-1\right)^{k}}{2k+1}n^{-2k-1}\quad.
\end{align*}
Implement a function that computes the series for $\arctan\frac{1}{n}$
up to a given number of terms, and compute an approximation of $\pi$
using this formula. Show that about $12$ terms of the series are
already sufficient for a full-precision \lstinline!Double! approximation
of $\pi$.

\subsubsection{Exercise \label{subsec:ch1-aggr-Exercise-2}\ref{subsec:ch1-aggr-Exercise-2}}

Using the function \lstinline!isPrime!, check numerically the Euler
product\index{Euler product} formula\footnote{\texttt{\href{https://en.wikipedia.org/wiki/Proof_of_the_Euler_product_formula_for_the_Riemann_zeta_function}{https://en.wikipedia.org/wiki/Proof\_of\_the\_Euler\_product\_formula\_for\_the\_Riemann\_zeta\_function}}}
for the Riemann\textsf{'}s zeta function\index{Riemann\textsf{'}s zeta function} $\zeta\left(4\right)$.
It is known\footnote{\texttt{\href{https://ocw.mit.edu/courses/mathematics/18-104-seminar-in-analysis-applications-to-number-theory-fall-2006/projects/chan.pdf}{https://tinyurl.com/yxey4tsd}}}
that $\zeta\left(4\right)=\frac{\pi^{4}}{90}$:
\[
\zeta\left(4\right)=\prod_{k\geq2;~k\text{ is prime}}\frac{1}{1-\frac{1}{p^{4}}}=\frac{\pi^{4}}{90}\quad.
\]


\subsection{Transformation}

\subsubsection{Exercise \label{subsec:ch1-transf-Exercise-1}\ref{subsec:ch1-transf-Exercise-1}}

Define a function \texttt{}\lstinline!add20! of type \texttt{}\lstinline!List[List[Int]] => List[List[Int]]!
that adds $20$ to every element of every inner list. A sample test:
\begin{lstlisting}
scala> add20( List( List(1), List(2, 3) ) )
res0: List[List[Int]] = List(List(21), List(22, 23))
\end{lstlisting}


\subsubsection{Exercise \label{subsec:ch1-transf-Exercise-2}\ref{subsec:ch1-transf-Exercise-2}}

An integer $n$ is called a \textsf{``}$3$-factor\textsf{''} if it is divisible by
only three different integers $j$ such that $2\leq j<n$. Compute
the set of all \textsf{``}$3$-factor\textsf{''} integers $n$ among $n\in[1,...,1000]$
.

\subsubsection{Exercise \label{subsec:ch1-transf-Exercise-3}\ref{subsec:ch1-transf-Exercise-3}}

Given a function \lstinline!f: Int => Boolean!, an integer $n$ is
called a \textsf{``}$3$-$f$\textsf{''} if there are only three different integers
$j\in[1,...,n]$ such that $f(j)$ returns \lstinline!true!. Define
a function that takes $f$ as an argument and returns a sequence of
all \textsf{``}$3$-$f$\textsf{''} integers among $n\in[1,...,1000]$. What is the
type of that function? Implement Exercise~\ref{subsec:ch1-transf-Exercise-2}
using that function.

\subsubsection{Exercise \label{subsec:ch1-transf-Exercise-4}\ref{subsec:ch1-transf-Exercise-4}}

Define a function \lstinline!see100! of type \texttt{}\lstinline!List[List[Int]] => List[List[Int]]!
that selects only those inner lists whose largest value is at least
$100$. Test with:
\begin{lstlisting}
scala> see100( List( List(0, 1, 100), List(60, 80), List(1000) ) )
res0: List[List[Int]] = List(List(0, 1, 100), List(1000))
\end{lstlisting}


\subsubsection{Exercise \label{subsec:ch1-transf-Exercise-5}\ref{subsec:ch1-transf-Exercise-5}}

Define a function of type \texttt{}\lstinline!List[Double] => List[Double]!
that \textsf{``}normalizes\textsf{''} the list: it finds the element having the largest
absolute value and, if that value is nonzero, divides all elements
by that value and returns a new list; otherwise returns the original
list. Test with:
\begin{lstlisting}
scala> normalize(List(1.0, 4.0, 2.0))
res0: List[Double] = List(0.25, 1.0, 0.5)
\end{lstlisting}


\section{Discussion}

\subsection{Functional programming as a paradigm}

Functional programming\index{functional programming paradigm} (FP)
is a \textbf{paradigm}\index{paradigm of programming} of programming
\textemdash{} an approach that guides programmers to write code in
specific ways, applicable to a wide range of tasks.

The main idea of FP is to write code \emph{as a mathematical expression
or formula}. This approach allows programmers to derive code through
logical reasoning rather than through guessing, similarly to how books
on mathematics reason about mathematical formulas and derive results
systematically, without guessing or \textsf{``}debugging.\textsf{''} Like mathematicians
and scientists who reason about formulas, functional programmers can
\emph{reason about code} systematically and logically, based on rigorous
principles. This is possible only because code is written as a mathematical
formula.

Mathematical intuition is productive because it is backed by the vast
experience accumulated while working with data over millennia of human
history. It took centuries to invent flexible and powerful notation,
such as $\sum_{k\in S}p(k)$, and to develop the corresponding rules
of calculation. Functional programmers are fortunate to have these
reasoning tools at their disposal.

As we have seen, the Scala code for certain computational tasks corresponds
quite closely to mathematical formulas (although programmers do have
to write out some details that are omitted in the mathematical notation).
Just as in mathematics, large code expressions may be split into smaller
expressions when needed. Expressions can be easily reused, composed
in various ways, and written independently from each other. Over the
years, the FP community has developed a toolkit of functions (such
as \lstinline!map!, \texttt{}\lstinline!filter!, etc.) that proved
to be especially useful in real-life programming, although many of
them are not standard in mathematical literature.

Mastering FP involves practicing to reason about programs as formulas
\textsf{``}translated into code\textsf{''}, building up the specific kind of applied
mathematical intuition, and getting familiar with mathematical concepts
adapted to a programmer\textsf{'}s needs. The FP community has discovered a
number of specific design patterns founded on mathematical principles
but driven by practical necessities of programming. This book explains
those mathematical design patterns in detail, starting from code examples
and heuristic ideas, and building up the techniques of rigorous reasoning.

\subsection{Functional programming languages}

It is possible to apply the FP paradigm while writing code in any
programming language. However, some languages lack certain features
that make FP techniques much easier to use in practice. For example,
in a language such as Python or Ruby, one can productively use only
a limited number of FP idioms, such as the map/reduce operations.
More advanced FP constructions are impractical in these languages
because the required code becomes too hard to read and to write without
errors, which negates the advantages of rigorous reasoning about functional
programs.

Some programming languages, such as Haskell and OCaml, were designed
specifically for advanced use in the FP paradigm. Other languages,
such as ML, F\#, Scala, Swift, PureScript, Elm, and Rust, have different
design goals but still support enough FP features to be considered
FP languages. This book uses Scala, but the same constructions may
be implemented in other FP languages in a similar way. At the level
of detail needed in this book, the differences between languages such
as ML, OCaml, Haskell, F\#, Scala, Swift, PureScript, Elm, and Rust,
do not play a significant role.

\subsection{The mathematical meaning of \textsf{``}variables\textsf{''}}

The usage of variables in functional programming is similar to how
mathematical literature uses variables. In mathematics, \textbf{variables\index{variable}}
are used first of all as \emph{arguments} of functions; e.g., the
formula 
\[
f(x)=x^{2}+x
\]
contains the variable $x$ and defines a function $f$ that takes
$x$ as its argument (to be definite, assume that $x$ is an integer)
and computes the value $x^{2}+x$. The body of the function is the
expression $x^{2}+x$. 

Mathematics has the convention that a variable, such as $x$, does
not change its value within a formula. Indeed, there is no mathematical
notation even to talk about \textsf{``}changing\textsf{''} the value of $x$ \emph{inside}
the formula $x^{2}+x$. It would be quite confusing if a mathematics
textbook said \textsf{``}before adding the last $x$ in the formula $x^{2}+x$,
we change that $x$ by adding $4$ to it\textsf{''}. If the \textsf{``}last $x$\textsf{''}
in $x^{2}+x$ needs to have a $4$ added to it, a mathematics textbook
will just write the formula $x^{2}+x+4$.

Arguments of nameless functions are also immutable. Consider, for
example,
\[
f(n)=\sum_{k=0}^{n}\,(k^{2}+k)\quad.
\]
Here, $n$ is the argument of the function $f$, while $k$ is the
argument of the nameless function $k\rightarrow k^{2}+k$. Neither
$n$ nor $k$ can be \textsf{``}modified\textsf{''} in any sense within the expressions
where they are used. The symbols $k$ and $n$ stand for some integer
values, and these values are immutable. Indeed, it is meaningless
to say that we \textsf{``}modified the integer $4$\textsf{''}. In the same way, we
cannot modify $k$.

So, a variable in mathematics remains constant \emph{within} \emph{the
expression} where it is defined; in that expression, a variable is
essentially a \textsf{``}named constant\textsf{''}. Of course, a function $f$ can
be applied to different values $x$, to compute a different result
$f(x)$ each time. However, a given value of $x$ will remain unmodified
within the body of the function $f$ while $f(x)$ is being computed.

Functional programming adopts this convention from mathematics: variables
are immutable named constants. (Scala also has \emph{mutable} variables,
but we will not consider them in this book.)

In Scala, function arguments are immutable within the function body:
\begin{lstlisting}
def f(x: Int) = x * x + x // Cannot modify `x` here.
\end{lstlisting}

The \emph{type} of each mathematical variable (such as integer, vector,
etc.) is also fixed. Each variable is a value from a specific set
(e.g., the set of all integers, the set of all vectors, etc.). Mathematical
formulas such as $x^{2}+x$ do not express any \textsf{``}checking\textsf{''} that
$x$ is indeed an integer and not, say, a vector, in the middle of
evaluating $x^{2}+x$. The types of all variables are checked in advance.

Functional programming adopts the same view: Each argument of each
function must have a \textbf{type\index{types}} that represents the
set of possible allowed values for that function argument. The programming
language\textsf{'}s compiler will automatically check the types of all arguments
in advance, \emph{before} the program runs. A program that calls functions
on arguments of incorrect types will not compile.

The second usage of \textbf{variables\index{variable}} in mathematics
is to denote expressions that will be reused. For example, one writes:
let $z=\frac{x-y}{x+y}$ and now compute $\cos z+\cos2z+\cos3z$.
Again, the variable $z$ remains immutable, and its type remains fixed.

In Scala, this construction (defining an expression to be reused later)
is written with the \textsf{``}\lstinline!val!\textsf{''} syntax. Each variable defined
using \textsf{``}\lstinline!val!\textsf{''} is a named constant, and its type and
value are fixed at the time of definition. Type annotations for \textsf{``}\lstinline!val!'\textsf{'}s
are optional in Scala: for instance we could write 
\begin{lstlisting}
val x: Int = 123
\end{lstlisting}
or we could omit the type annotation \lstinline!:Int! and write more
concisely
\begin{lstlisting}
val x = 123
\end{lstlisting}
Here, it is clear that this \texttt{}\lstinline!x! is an integer.
Nevertheless, it is often helpful to write out the types. If we do
so, the compiler will check that the types match correctly and give
an error message whenever wrong types are used. For example, a type
error is detected when using a \lstinline!String! instead of an \lstinline!Int!:
\begin{lstlisting}
scala> val x: Int = "123"
<console>:11: error: type mismatch;
 found   : String("123")
 required: Int
        val x: Int = "123"
                     ^
\end{lstlisting}


\subsection{Iteration without loops}

Another distinctive feature of the FP paradigm is handling of iteration
without writing loops.

Iterative computations are ubiquitous in mathematics. As an example,
consider the formula for the standard deviation ($\sigma$) estimated
from a data sample $\left[x_{1},...,x_{n}\right]$:
\[
\sigma=\sqrt{\frac{1}{n-1}\sum_{i=1}^{n}x_{i}^{2}-\frac{1}{n\left(n-1\right)}\left(\sum_{i=1}^{n}x_{i}\right)^{2}}\quad.
\]
This expression is computed by iterating over values of the index
$i$. And yet, no mathematics textbook uses loops or says \textsf{``}now repeat
this formula ten times\textsf{''}. Indeed, it would be pointless to evaluate
a formula such as $x^{2}+x$ ten times, because the result of $x^{2}+x$
remains the same every time. It is also meaningless to \textsf{``}repeat\textsf{''}
an equation such as $\left(x-1\right)(x^{2}+x+1)=x^{3}-1$.

Instead of loops, mathematicians write \emph{expressions} such as
$\sum_{i=1}^{n}s_{i}$, where symbols such as $\sum_{i=1}^{n}$ denote
the results of entire iterative computations. Such computations are
defined using mathematical induction\index{mathematical induction}.
The FP paradigm has developed rich tools for translating mathematical
induction into code. This chapter focused on methods such as \lstinline!map!,
\lstinline!filter!, and \lstinline!sum!, which implement certain
kinds of iterative computations. These and other similar methods can
be combined in flexible ways, enabling programmers to write iterative
code without loops. For example, the computation of $\sigma$ according
to the formula shown above may be implemented by code that looks like
this:
\begin{lstlisting}
def sigma(xs: Seq[Double]): Double = {
  val n = xs.length.toDouble
  val xsum = xs.sum
  val x2sum = xs.map(x => x * x).sum
  math.sqrt(x2sum / (n - 1) - xsum * xsum / n / (n - 1))
}

scala> sigma(Seq(10, 20, 30))
res0: Double = 10.0
\end{lstlisting}

The programmer can avoid writing loops because all iterative computations
are delegated to functions such as \lstinline!map!, \lstinline!filter!,
\lstinline!sum!, and others. It is the job of the library and the
compiler to translate those high-level functions into low-level machine
code. The machine code \emph{will} likely contain loops; but the programmer
does not need to see that machine code or to reason about it.

\subsection{Nameless functions in mathematical notation\label{subsec:Nameless-functions-in-mathematical-notation}}

Functions in mathematics are mappings from one set to another. A function
does not necessarily \emph{need} a name; the mapping just needs to
be defined. However, nameless functions have not been widely used
in the conventional mathematical notation. It turns out that nameless
functions are important in functional programming because, in particular,
they allow programmers to write code with a straightforward and consistent
syntax.

Nameless functions contain bound variables that are invisible outside
the function\textsf{'}s scope. This property is directly reflected by the prevailing
mathematical conventions. Compare the formulas
\[
f\left(x\right)=\int_{0}^{x}\frac{dx}{1+x}\quad;\quad f\left(x\right)=\int_{0}^{x}\frac{dz}{1+z}\quad.
\]
The mathematical convention is that one may rename the integration
variable at will, and so these formulas define the same function $f$.

In programming, the only situation when a variable \textsf{``}may be renamed
at will\textsf{''} is when the variable represents an argument of a function.
It follows that the notations $\frac{dx}{1+x}$ and $\frac{dz}{1+z}$
correspond to a nameless function whose argument was renamed from
$x$ to $z$. In FP notation, this nameless function would be denoted
as $z\rightarrow\frac{1}{1+z}$, and the integral rewritten as code
such as
\begin{lstlisting}
integration(0, x, { z => 1.0 / (1 + z) } )
\end{lstlisting}
Now consider the traditional mathematical notations for summation,
for instance,
\[
\sum_{k=0}^{x}\frac{1}{1+k}\quad.
\]
In that sum, the bound variable $k$ is introduced under the $\sum$
symbol; but in integrals, the bound variable follows the special symbol
\textsf{``}$d$\textsf{''}. This notational inconsistency could be removed if we were
to use nameless functions explicitly, for example:
\begin{align*}
\text{denote summation by }\sum_{0}^{x} & \left(k\rightarrow\frac{1}{1+k}\right)\text{ instead of }\sum_{k=0}^{x}\frac{1}{1+k}\quad,\\
\text{denote integration by }\int_{0}^{x} & \left(z\rightarrow\frac{1}{1+z}\right)\text{ instead of }\int_{0}^{x}\frac{dz}{1+z}\quad.
\end{align*}
In this notation, the new summation symbol $\sum_{0}^{x}$ does not
mention the name \textsf{``}$k$\textsf{''} but takes a function as an argument. Similarly,
the new integration symbol $\int_{0}^{x}$ does not mention \textsf{``}$z$\textsf{''}
and does not use the special symbol \textsf{``}$d$\textsf{''} but now takes a function
as an argument. Written in this way, the operations of summation and
integration become \emph{functions} that take functions as arguments.
The above summation may be written in a consistent and straightforward
manner as a Scala function:
\begin{lstlisting}
summation(0, x, { y => 1.0 / (1 + y) } )
\end{lstlisting}

We could implement \texttt{}\lstinline!summation(a, b, g)! as
\begin{lstlisting}
def summation(a: Int, b: Int, g: Int => Double): Double = (a to b).map(g).sum

scala> summation(1, 10, x => math.sqrt(x))
res0: Double = 22.4682781862041
\end{lstlisting}

Integration requires longer code since the computations are more complicated.
\index{Simpson\textsf{'}s rule}Simpson\textsf{'}s rule\footnote{\texttt{\href{https://en.wikipedia.org/wiki/Simpson\%27s_rule}{https://en.wikipedia.org/wiki/Simpson\%27s\_rule}}}
is an algorithm for approximate numerical integration, defined by
the formulas
\begin{align*}
\text{integration}\left(a,b,g,\varepsilon\right) & =\frac{\delta}{3}\big(g(a)+g(b)+4s_{1}+2s_{2}\big)\quad,\\
\text{where }~~~n & =2\left\lfloor \frac{b-a}{\varepsilon}\right\rfloor ,\quad\delta_{x}=\frac{b-a}{n}\quad,\\
s_{1}=\sum_{k=1,3,...,n-1}g(a+k\delta_{x}) & \quad,\quad\quad s_{2}=\sum_{k=2,4,...,n-2}g(a+k\delta_{x})\quad.
\end{align*}
 A straightforward line-by-line translation of these formulas into
Scala is
\begin{lstlisting}
def integration(a: Double, b: Double, g: Double => Double, eps: Double): Double = {
   // First, we define some helper values and functions corresponding
   // to the definitions "where n = ..." in the mathematical formulas.
   val n: Int = 2 * ((b - a) / eps).toInt
   val delta_x = (b - a) / n
   val s1 = (1 to (n - 1) by 2).map { k => g(a + k * delta_x) }.sum
   val s2 = (2 to (n - 2) by 2).map { k => g(a + k * delta_x) }.sum
   // Now we can write the expression for the final result.
   delta_x / 3 * (g(a) + g(b) + 4 * s1 + 2 * s2)
}

scala> integration(0, 5, x => x*x*x*x, eps = 0.01)     // The exact answer is 625.
res0: Double = 625.0000000004167

scala> integration(0, 7, x => x*x*x*x*x*x, eps = 0.01) // The exact answer is 117649.
res1: Double = 117649.00000014296
\end{lstlisting}

The entire code is one large \emph{expression}, with a few sub-expressions
(\lstinline!s1!, \lstinline!s2!, etc.) defined for convenience in
the \textbf{local scope}\index{local scope} of the function. In other
words, this code is written in the FP paradigm.

\subsection{Named and nameless expressions and their uses}

It is a significant advantage if a programming language supports unnamed
(or \textsf{``}nameless\textsf{''}) expressions. To see this, consider a familiar
situation where we take the absence of names for granted.

In today\textsf{'}s programming languages, we may directly write expressions
such as \texttt{}\lstinline!(x+123)*y/(4+x)!. Note that the entire
expression does not need to have a name. Parts of that expression
(e.g., the sub-expressions \texttt{}\lstinline!x+123! or \lstinline!4+x!)
also do not have separate names. It would be inconvenient if we \emph{needed}
to assign a name to each sub-expression. The code for \lstinline!(x+123)*y/(4+x)!
would then look like this:

\begin{lstlisting}
{
  val r0 = 123
  val r1 = x + r0
  val r2 = r1 * y
  val r3 = 4 
  val r4 = r3 + x
  val r5 = r2 / r4     // Do we still remember what `r2` means?
  r5
}
\end{lstlisting}

This style of programming resembles assembly languages\index{assembly language},
where \emph{every} sub-expression \textemdash{} that is, every step
of every calculation \textemdash{} must be assigned a separate memory
address or a CPU register.

Programmers become more productive when their programming language
supports nameless expressions. This is also common practice in mathematics;
names are assigned when needed, but most expressions remain nameless.

It is similarly useful if data structures can be created without names.
For instance, a \textbf{dictionary}\index{dictionary} (also called
a \textsf{``}map\textsf{''}) is created in Scala with this code:

\begin{wrapfigure}{l}{0.38\columnwidth}%
\vspace{-0.8\baselineskip}
\begin{lstlisting}
Map("a" -> 1, "b" -> 2, "c" -> 3)
\end{lstlisting}

\vspace{-1.2\baselineskip}
\end{wrapfigure}%

\noindent This is a nameless expression whose value is a dictionary.
In programming languages that do not have such a construction, programmers
have to write repetitive code that creates an initially empty dictionary
and then fills it step by step with values:

\begin{wrapfigure}{l}{0.38\columnwidth}%
\vspace{-0.7\baselineskip}
\begin{lstlisting}[language=Java]
// Scala code creating a dictionary:
Map("a" -> 1, "b" -> 2, "c" -> 3)

// Shortest Java code for the same:
new HashMap<String, Integer>() {{
   put("a", 1);
   put("b", 2);
   put("c", 3);
}};
\end{lstlisting}

\vspace{0\baselineskip}
\end{wrapfigure}%
\begin{wraptable}{r}{0.6\columnwidth}%
\begin{centering}
\vspace{-8\baselineskip}
\begin{tabular}{|c|c|c|}
\hline 
\textbf{\small{}Language} & \textbf{\small{}Year} & \textbf{\small{}Code for }{\small{}$k\rightarrow k+1$}\tabularnewline
\hline 
\hline 
{\footnotesize{}$\lambda$-calculus} & {\footnotesize{}1936} & $\lambda k.~add~k~1$\tabularnewline
\hline 
{\footnotesize{}typed $\lambda$-calculus} & {\footnotesize{}1940} & $\lambda k:int.~add~k~1$\tabularnewline
\hline 
{\footnotesize{}LISP} & {\footnotesize{}1958} & \texttt{\footnotesize{}}\lstinline!(lambda (k) (+ k 1))!\tabularnewline
\hline 
{\footnotesize{}Standard ML} & {\footnotesize{}1973} & \texttt{\footnotesize{}}\lstinline!fn (k: int) => k + 1!\tabularnewline
\hline 
{\footnotesize{}Caml} & {\footnotesize{}1985} & \lstinline!fun (k: int) -> k + 1!\tabularnewline
\hline 
{\footnotesize{}Haskell} & {\footnotesize{}1990} & \lstinline!\ k -> k + 1!\tabularnewline
\hline 
{\footnotesize{}Oz} & {\footnotesize{}1991} & \lstinline!fun {$ K} K + 1!\tabularnewline
\hline 
{\footnotesize{}R} & {\footnotesize{}1993} & \lstinline!function(k) k + 1!\tabularnewline
\hline 
{\footnotesize{}Python 1.0} & {\footnotesize{}1994} & \lstinline!lambda k: k + 1!\tabularnewline
\hline 
{\footnotesize{}JavaScript} & {\footnotesize{}1995} & \lstinline!function(k) { return k + 1; }!\tabularnewline
\hline 
{\footnotesize{}Mercury} & {\footnotesize{}1995} & \lstinline!func(K) = K + 1!\tabularnewline
\hline 
{\footnotesize{}Ruby} & {\footnotesize{}1995} & \lstinline!lambda { |k| k + 1 }!\tabularnewline
\hline 
{\footnotesize{}Lua 3.1} & {\footnotesize{}1998} & \lstinline!function(k) return k + 1 end!\tabularnewline
\hline 
{\footnotesize{}Scala} & {\footnotesize{}2003} & \lstinline!(k: Int) => k + 1!\tabularnewline
\hline 
{\footnotesize{}F\#} & {\footnotesize{}2005} & \lstinline!fun (k: int) -> k + 1!\tabularnewline
\hline 
{\footnotesize{}C\# 3.0} & {\footnotesize{}2007} & \lstinline!delegate(int k) { return k + 1; }!\tabularnewline
\hline 
{\footnotesize{}Clojure} & {\footnotesize{}2009} & \lstinline!fn [k] (+ k 1)!\tabularnewline
\hline 
{\footnotesize{}C++ 11} & {\footnotesize{}2011} & \lstinline![] (int k) { return k + 1; }!\tabularnewline
\hline 
{\footnotesize{}Go} & {\footnotesize{}2012} & \lstinline!func(k int) { return k + 1 }!\tabularnewline
\hline 
{\footnotesize{}Julia} & {\footnotesize{}2012} & \lstinline!function(k:: Int) k + 1 end!\tabularnewline
\hline 
{\footnotesize{}Kotlin} & {\footnotesize{}2012} & \lstinline!{ k: Int -> k + 1 }!\tabularnewline
\hline 
{\footnotesize{}Swift} & {\footnotesize{}2014} & \lstinline!{ (k:int) -> int in return k + 1 }!\tabularnewline
\hline 
{\footnotesize{}Java 8} & {\footnotesize{}2014} & \lstinline!(int k) -> k + 1!\tabularnewline
\hline 
{\footnotesize{}Rust} & {\footnotesize{}2015} & \lstinline!|k: i32| k + 1!\tabularnewline
\hline 
\end{tabular}
\par\end{centering}
\caption{Nameless functions in programming languages.\label{lambda-functions-table}}
\vspace{-3\baselineskip}
\end{wraptable}%

\noindent Nameless functions are useful for the same reason as nameless
values of other types: they allow us to build larger programs from
simpler parts in a uniform way.

\subsection{Historical perspective on nameless functions}

Nameless functions were first used in 1936 in a theoretical programming
language called \textsf{``}$\lambda$-calculus\index{\$@$\lambda$-calculus}\textsf{''}.
In that language,\footnote{Although called a \textsf{``}calculus,\textsf{''} it is a (drastically simplified)
programming language, not related to differential or integral calculus.
Also, the letter $\lambda$ has no particular significance; it plays
a purely syntactic role in the $\lambda$-calculus. Practitioners
of functional programming usually do not need to study any $\lambda$-calculus.
All practically relevant knowledge related to $\lambda$-calculus
is explained in Chapter~\ref{chap:Higher-order-functions} of this
book.} all functions are nameless and have a single argument. The letter
$\lambda$ is a syntax separator denoting function arguments in nameless
functions. For example, the nameless function $x\rightarrow x+1$
could be written as $\lambda x.~add~x~1$ in $\lambda$-calculus,
if it had a function $add$ for adding integers (which it does not).

In most programming languages that were in use until around 1990,
all functions required names. But by 2015, most languages added support
for nameless functions, because programming in the map/reduce style
(which invites frequent use of nameless functions) turned out to be
immensely productive. Table\ \ref{lambda-functions-table} shows
the year when nameless functions were introduced in each language.

What this book calls a \textsf{``}nameless function\textsf{''} is also called anonymous
function,\index{anonymous function!see \textsf{``}nameless functions\textsf{''}} function
expression, function literal, closure, \index{lambda-function!see \textsf{``}nameless function\textsf{''}}lambda
function, lambda expression, or just a \textsf{``}lambda\textsf{''}.
